/*****************************************************************************
 * dict.c: Basic splay-tree based dictionary
 *****************************************************************************
 * Copyright (C) 2012
 *
 * Authors: Dan Larkin <danielhlarkin@gmail.com>
 *          Yonatan Naamad <cached@gmail.com>
 *
 * This program is free software; you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation; either version 2 of the License, or
 * (at your option) any later version.
 *
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *****************************************************************************/

#include "dict.h"
#include <string.h>

typedef struct cpm_dict_pair
{
    cpm_dict_node *left;
    cpm_dict_node *right;
} cpm_dict_pair;

static cpm_dict_node* cpm_dict_join( cpm_dict *dict, cpm_dict_pair pair );
static cpm_dict_pair cpm_dict_split( cpm_dict *dict, int split_left );
static void cpm_dict_splay( cpm_dict *dict, cpm_dict_node *node );
static void cpm_dict_rotate_left( cpm_dict *dict, cpm_dict_node *node );
static void cpm_dict_rotate_right( cpm_dict *dict, cpm_dict_node *node );

cpm_dict* cpm_dict_init( int32_t key_len )
{
    cpm_dict *dict = calloc( 1, sizeof( cpm_dict ) );
    dict->key_len = key_len;

    return dict;
}

void cpm_dict_insert( cpm_dict *dict, void *element )
{
    cpm_dict_node *node = calloc( 1, sizeof( cpm_dict_node ) );
    node->element = element;

    cpm_dict_lookup( dict, element );
    int split_left = ( dict->root == NULL ||
        memcmp( element, dict->root->element, dict->key_len ) < 0 ) ? 1 : 0;
    cpm_dict_pair pair = cpm_dict_split( dict, split_left );

    node->left = pair.left;
    node->right = pair.right;

    if( pair.left != NULL )
        pair.left->parent = node;
    if( pair.right != NULL )
        pair.right->parent = node;

    dict->root = node;
}

void cpm_dict_delete( cpm_dict *dict, cpm_dict_node *node )
{
    cpm_dict_splay( dict, node );

    cpm_dict_pair pair;
    pair.left = node->left;    
    pair.right = node->right;

    if( pair.left != NULL )
        pair.left->parent = NULL;
    if( pair.right != NULL )
        pair.right->parent = NULL;

    dict->root = cpm_dict_join( dict, pair );

    free( node );
}

cpm_dict_node* cpm_dict_lookup( cpm_dict *dict, void *key )
{
    if( dict->root == NULL )
        return NULL;

    cpm_dict_node *target = NULL;
    cpm_dict_node *current = dict->root;
    cpm_dict_node *next = current;
    int cmp;
    
    while( next != NULL )
    {
        current = next;
        cmp = memcmp( key, current->element, dict->key_len );
        if( cmp == 0 )
        {
            target = current;
            break;
        }

        if( cmp < 0 )
            next = current->left;
        else
            next = current->right;
    }

    cpm_dict_splay( dict, current );

    return target;
}

static cpm_dict_node* cpm_dict_join( cpm_dict *dict, cpm_dict_pair pair )
{
    if( pair.left == NULL )
        return pair.right;
    if( pair.right == NULL )
        return pair.left;

    cpm_dict_node *current = pair.left;
    while( current->right != NULL )
        current = current->right;

    cpm_dict_splay( dict, current );
    current->right = pair.right;
    if( pair.right != NULL )
        pair.right->parent = current;

    return current;
}

static cpm_dict_pair cpm_dict_split( cpm_dict *dict, int split_left )
{
    cpm_dict_pair pair = { NULL, NULL };

    if( split_left )
    {
        pair.right = dict->root;
        if( dict->root != NULL && dict->root->left != NULL )
        {
            pair.left = dict->root->left;
            pair.left->parent = NULL;
            pair.right->left = NULL;
        }
    }
    else
    {
        pair.left = dict->root;
        if( dict->root != NULL && dict->root->right != NULL )
        {
            pair.right = dict->root->right;
            pair.right->parent = NULL;
            pair.left->right = NULL;
        }
    }

    return pair;
}

static void cpm_dict_splay( cpm_dict *dict, cpm_dict_node *node )
{
    while( node->parent != NULL )
    {
        if( node->parent->parent == NULL )
        {
            // single terminal rotation
            if( node->parent->left == node )
                cpm_dict_rotate_right( dict, node );
            else
                cpm_dict_rotate_left( dict, node );
                
            break;
        }

        if( node->parent->left == node )
        {
            if( node->parent->parent->left == node->parent )
            {
                // zig-zig left
                cpm_dict_rotate_right( dict, node->parent );
                cpm_dict_rotate_right( dict, node );
            }
            else
            {
                // zig-zag left
                cpm_dict_rotate_right( dict, node );
                cpm_dict_rotate_left( dict, node );
            }
        }
        else
        {
            if( node->parent->parent->right == node->parent )
            {
                // zig-zig right
                cpm_dict_rotate_left( dict, node->parent );
                cpm_dict_rotate_left( dict, node );
            }
            else
            {
                // zig-zag right
                cpm_dict_rotate_left( dict, node );
                cpm_dict_rotate_right( dict, node );
            }
        }
    }
}

static void cpm_dict_rotate_left( cpm_dict *dict, cpm_dict_node *node )
{
    cpm_dict_node *old_parent = node->parent;
    node->parent = old_parent->parent;
    old_parent->parent = node;
    
    if( node->parent != NULL )
    {
        if( node->parent->left == old_parent )
            node->parent->left = node;
        else
            node->parent->right = node;
    }

    old_parent->right = node->left;
    node->left = old_parent;

    if( old_parent->right != NULL )
        old_parent->right->parent = old_parent;    
        
    if( dict->root == old_parent )
        dict->root = node;
}

static void cpm_dict_rotate_right( cpm_dict *dict, cpm_dict_node *node )
{
    cpm_dict_node *old_parent = node->parent;
    node->parent = old_parent->parent;
    old_parent->parent = node;

    if( node->parent != NULL )
    {
        if( node->parent->left == old_parent )
            node->parent->left = node;
        else
            node->parent->right = node;
    }

    old_parent->left = node->right;
    node->right = old_parent;

    if( old_parent->left != NULL )
        old_parent->left->parent = old_parent;    
        
    if( dict->root == old_parent )
        dict->root = node;
}
